Many electronic devices have been used for data storage, such as Hard Disk Drives (HDDs) and Solid State Drives (SSDs). Compared with HDDs, SSDs often have fewer mechanical defects and lower power consumption, and execute read and write operations more quickly in some instances.
As shown in FIG. 1, a data storage device 100 (e.g., a SSD) often includes a controller unit 102, a volatile memory 104, and a non-volatile memory 106. User data may be stored on the non-volatile memory 106 so that the user data will not be lost upon power failure. For example, the volatile memory 104 may include one or more dynamic random-access memory (DRAM) devices, and the non-volatile memory 106 may include one or more flash memory devices.
A flash memory device (e.g., a NAND flash memory) is often divided into storage blocks, and each storage block includes multiple pages. Typically, reading and programming a flash memory device can be performed on a page basis, but erasure can only be performed on a block basis. Moreover, a flash memory device may not support an in-place update. That is, a new page cannot be written over an old page at a same physical location unless the entire block is erased first. In addition, a flash memory device has a finite number of program-erase cycles before the integrity of the storage begins to deteriorate.
An internal software layer, Flash Translation Layer (FTL), is often implemented for managing data storage in the device 100. Major functions of an FTL include logic-to-physical address translation, garbage collection which reclaims used blocks, and wear leveling to increase lifespan of a flash memory device. In order to execute these functions, many data structures can be used for the FTL, such as an address mapping table (e.g., a page-level mapping or a block-level mapping), a pool of free blocks, and list of garbage blocks with erase counts. These data structures are typically called FTL metadata.